package Tree;

public class _96_UniqueBinarySearchTrees {
    int res = 0;
    int size = 0;
    boolean[] visit;
    public int numTrees(int n) {
        this.visit = new boolean[n + 1];
        this.size = n;
        for (int i = 1; i <= size; i++) {
            System.out.println(i);
            visit[i] = true;
            getBST(i,1,i,Integer.MIN_VALUE);
            getBST(i, 1, Integer.MAX_VALUE, i);
            visit[i] = false;
        }
        return res;
    }

    public void getBST(int val,int count,int max,int min) {
        if (count == size) {
            res++;
            return;
        } else {
            for (int i = 1; i <=size ; i++) {
                if (!visit[i]) {
                    if (i > min && i < max) {
                        if (i!=val) {
                            visit[i] = true;
                            getBST(i,count+1,Math.min(i, max),min);
                            visit[i] = false;
                            visit[i] = true;
                            getBST(i,count+1,max,Math.max(i, min));
                            visit[i] = false;
                        }
                    }
                }
            }
        }
    }
}
